The inventive concept relates to a modular multiplier apparatus, and more particularly, to a modular multiplier apparatus with a reduced critical path of an arithmetic operation.
The Rivest Shamir Adleman (RSA) algorithm is an Internet cryptography and authentication system in which encryption and decryption are performed using a public key and a private key generated using two large prime numbers. RSA involves a public key and a private key, which are constituted by performing multiplication of two large prime numbers and an additional arithmetic operation thereon. Information (in particular, an e-mail) used in the Internet are encrypted and decrypted using the public key and the private key. A principle of the RSA algorithm is disclosed at the RSA Internet web site at http://www.rsa.com. The time required for encryption and decryption in a public-key cryptography system increases as the lengths of keys used increase. In order to solve a problem that the number of calculations increases in an RSA cryptography system and an operation time required for a large amount of calculations increases, an elliptic curve algorithm has recently been considered as an alternative to the RSA algorithm.
In a public-key cryptography system such as an RSA algorithm system or elliptic curve cryptography system, a modular operation is performed on very large numbers. Thus, the performance of a security system is determined by the speed and efficiency of the modular operation. In particular, in the case of the RSA algorithm, at least 2,048-bit keys are used for high security, and it is desired that 4,096-bit keys be used in the future. Under such circumstances, it is very important in several applied fields to implement the modular operation at high speed.
There are several algorithms with which modular multiplication is performed. Among them, a Montgomery modular multiplication technique is widely used to implement hardware. Research on implementing hardware by using the Montgomery modular multiplication technique has been widely conducted for the last 20 years. However, in most cases, radix 2, radix 4, or radix 8 is used. It is well known that increasing radix is the best way to increase the operation speed. However, as an exponent of radix increases, a procedure of determining a quotient becomes complicated. Thus, there is a limitation in increasing an exponent of radix.
In a high radix operation, a pipeline method is widely used to reduce a critical path of an arithmetic operation. Due to an operation characteristic of the Montgomery modular multiplication, the result of adding the previous result of an arithmetic operation and a product of constants used in calculation is needed so as to obtain a current quotient. When the pipeline method is used, values such as the previous result of an arithmetic operation and the product of constants used in calculation do not need to be separately obtained.
In the Montgomery modular multiplication using radix 2k (where k is an integer), subtraction is performed to a lower k-bit. In this procedure, in order to obtain the final result in a non-redundant form, at least k-bit carry propagation occurs, which causes an operation delay of about 12% to about 40%.